#include <linux/sched.h>
#include <linux/kernel.h>

static inline void oom(void)
{
    printk("out of memory\n");
    while (1);
}

#define invalidate() \
__asm__("movl %%eax, %%cr3"::"a"(0))

#define LOW_MEM 0x100000
#define PAGING_MEMORY (15*1024*1024)
#define PAGING_PAGES (PAGING_MEMORY>>12)
#define MAP_NR(addr) (((addr)-LOW_MEM)>>12)
#define USED 100

static long HIGH_MEMORY = 0;

#define copy_page(from, to) \
__asm__("cld\n\trep\n\tmovsl"::"S"(from), "D"(to), "c"(1024))

static unsigned char mem_map[PAGING_PAGES] = {0, };    // 记录内存页面的使用情况

/**
 * 寻找空闲页
 * @return  0：没找到空闲页
 *          其他：空闲页地址
 */
unsigned long get_free_page(void)
{
    unsigned long __res;

    __asm__("std\n\trepne\n\tscasb\n\t"
        "jne 1f\n\t"
        "movb $1, 1(%%edi)\n\t"
        "sall $12, %%ecx\n\t"
        "addl %2, %%ecx\n\t"
        "movl %%ecx, %%edx\n\t"
        "movl $1024, %%ecx\n\t"
        "leal 4092(%%edx), %%edi\n\t"
        "rep\n\tstosl\n\t"
        "movl %%edx, %%eax\n"
        "1:"
        :"=a"(__res)
        :"0"(0), "i"(LOW_MEM), "c"(PAGING_PAGES),
        "D"(mem_map + PAGING_PAGES - 1)
        );
    return __res;
}

void free_page(unsigned long addr)
{
    if (addr < LOW_MEM)
        return;
    if (addr >= HIGH_MEMORY)
        panic("trying to free nonexistent page");
    addr -= LOW_MEM;
    addr >>= 12;
    if (mem_map[addr]--)
        return;
    mem_map[addr] = 0;
    panic("trying to free free page");
}

/**
 * 释放作为页表的页面
 * @param from 新任务代码段基址
 * @param size 父进程代码段长度
 */
int free_page_tables(unsigned long from, unsigned long size)
{
    unsigned long *pg_table;
    unsigned long *dir, nr;

    if (from & 0x3fffff)
        panic("free_page_tables called with wrong alignment");
    if (!from)
        panic("Trying to free up swapper memory space");
    size = (size + 0x3fffff) >> 22;     // 页目录项数量
    dir = (unsigned long *) ((from >> 22) << 2); /* _pg_dir = 0 */
    for ( ; size-- > 0; dir++) {
        if (!(1 & *dir))
            continue;
        pg_table = (unsigned long *) (0xfffff000 & *dir);
        for (nr = 0; nr < 1024; nr++) {
            if (1 & *pg_table)
                free_page(0xfffff000 & *pg_table);
            *pg_table = 0;
            pg_table++;
        }
        free_page(0xfffff000 & *dir);
        *dir = 0;
    }
    invalidate();
    return 0;
}

/**
 * 拷贝页表
 * @param from  父进程代码段基址
 * @param to    子进程代码段基址
 * @param size  父进程代码段长度
 */
int copy_page_tables(unsigned long from, unsigned long to, long size)
{
    unsigned long *from_page_table;
    unsigned long *to_page_table;
    unsigned long this_page;
    unsigned long *from_dir, *to_dir;
    unsigned long nr;

    if ((from & 0x3fffff) || (to & 0x3fffff))   // 需要4MB对齐
        panic("copy_page_tables called with wrong alignment");
    from_dir = (unsigned long *) ((from >> 22) << 2);
    to_dir = (unsigned long *) ((to >> 22) << 2);
    size = ((unsigned) (size + 0x3fffff)) >> 22;    // 页目录项数量
    for( ; size-- > 0; from_dir++, to_dir++) {
        if (1 & *to_dir)
            panic("copy_page_tables: already exist");
        if (!(1 & *from_dir))
            continue;
        from_page_table = (unsigned long *) (0xfffff000 & *from_dir);
        if (!(to_page_table = (unsigned long *) get_free_page()))
            return -1;    // 无空闲页面
        *to_dir = ((unsigned long) to_page_table) | 7;
        nr = (from == 0) ? 0xA0 : 1024; // 如果是复制任务0，只复制前160个页面
        for ( ; nr-- > 0; from_page_table++, to_page_table++) {
            this_page = *from_page_table;
            if (!(1 & this_page))
                continue;
            this_page &= ~2;    // 只有读权限
            *to_page_table = this_page;
            if (this_page > LOW_MEM) {
                *from_page_table = this_page;
                this_page -= LOW_MEM;
                this_page >>= 12;
                mem_map[this_page]++;
            }
        }
    }
    invalidate();
    return 0;
}

unsigned long put_page(unsigned long page, unsigned long address)
{
    unsigned long tmp, *page_table;

    if (page < LOW_MEM || page >= HIGH_MEMORY)
        printk("Trying to put page %p at %p\n", page, address);
    if (mem_map[(page - LOW_MEM) >> 12] != 1)
        printk("mem_map disagrees with %p at %p\n", page, address);
    page_table = (unsigned long *)((address >> 20) & 0xffc);    // 页目录项
    if (*page_table & 1)    // 是否存在页表
        page_table = (unsigned long *)(0xfffff000 & *page_table);
    else {
        tmp = get_free_page();
        if (!tmp)
            return 0;
        *page_table = tmp | 7;  // 页表已存在，可读可写，用户可访问页表中的页
        page_table = (unsigned long *)tmp;
    }
    page_table[(address >> 12) & 0x3ff] = page | 7; // 页面已存在，可读可写，用户可访问该页
    return page;
}

void un_wp_page(unsigned long *table_entry)
{
    unsigned long old_page, new_page;

    old_page = 0xfffff000 & *table_entry;
    if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)] == 1) {    // 如果页面已存在
        *table_entry |= 2;
        invalidate();
        return;
    }
    new_page = get_free_page();
    if (!new_page)
        oom();
    if (old_page >= LOW_MEM)
        mem_map[MAP_NR(old_page)]--;
    *table_entry = new_page | 7;
    invalidate();
    copy_page(old_page,new_page);
}

void do_wp_page(unsigned long error_code, unsigned long address)
{
    un_wp_page((unsigned long *)
        (((address>>10) & 0xffc) + (0xfffff000 & 
        *((unsigned long *) ((address>>20) & 0xffc)))));

}

void write_verify(unsigned long address)
{
    unsigned long page;

    if (!((page = *((unsigned long *) ((address >> 20) & 0xffc))) & 1))     // 页面是否存在
        return;
    page &= 0xfffff000;
    page += ((address >> 10) & 0xffc);
    if ((3 & *(unsigned long *) page) == 1)  // 如果没有写权限
        un_wp_page((unsigned long *) page);
    return;
}

void get_empty_page(unsigned long address)
{
    unsigned long tmp;

    tmp = get_free_page();
    if (!tmp || !put_page(tmp, address)) {
        free_page(tmp);
        oom();
    }
}

static int try_to_share(unsigned long address, struct task_struct *p)
{
    unsigned long from;
    unsigned long to;
    unsigned long from_page;
    unsigned long to_page;
    unsigned long phys_addr;

    from_page = to_page = ((address >> 20) & 0xffc);
    from_page += ((p->start_code >> 20) & 0xffc);
    to_page += ((current->start_code >> 20) & 0xffc);

    from = *(unsigned long *)from_page;
    if (!(from & 1))    // 页面是否被修改
        return 0;
    from &= 0xfffff000;
    from_page = from + ((address >> 10) & 0xffc);
    phys_addr = *(unsigned long *)from_page;
    
    if ((phys_addr & 0x41) != 0x01)
        return 0;
    phys_addr &= 0xfffff000;
    if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM)
        return 0;
    to = *(unsigned long *)to_page;
    if (!(to & 1)) {    // 当前进程是否存在该页表
        to = get_free_page();
        if (to)
            *(unsigned long *)to_page = to | 7;
        else
            oom();
    }
    to &= 0xfffff000;
    to_page = to + ((address >> 10) & 0xffc);   // 找到页表项
    if (1 & *(unsigned long *)to_page)
        panic("try_to_share: to_page already exists");
    
    *(unsigned long *)from_page &= ~2;  // 只读
    *(unsigned long *)to_page = *(unsigned long *)from_page;    // 修改页表项
    invalidate();
    phys_addr -= LOW_MEM;
    phys_addr >>= 12;
    mem_map[phys_addr]++;   // 引用数加1
    return 1;
}

static int share_page(unsigned long address)
{
    struct task_struct **p;

    if (!current->executable)
        return 0;
    if (current->executable->i_count < 2)
        return 0;
    for (p = &LAST_TASK; p > &FIRST_TASK; --p) {
        if (!*p)
            continue;
        if (current == *p)
            continue;
        if ((*p)->executable != current->executable)
            continue;
        if (try_to_share(address, *p))
            return 1;
    }
    return 0;
}

void do_no_page(unsigned long error_code, unsigned long address)
{
    int nr[4];
    unsigned long tmp;
    unsigned long page;
    int block, i;

    address &= 0xfffff000;
    tmp = address - current->start_code;
    if (!current->executable || tmp >= current->end_data) {
        get_empty_page(address);
        return;
    }
    if (share_page(tmp))
        return;
    page = get_free_page();
    if (!page)
        oom();

    block = 4 + tmp / BLOCK_SIZE;   // 从第4个逻辑块开始才是LOAD段
    for (i = 0; i < 4; block++, i++)
        nr[i] = bmap(current->executable, block);
    bread_page(page, current->executable->i_dev, nr);
    i = tmp + 4096 - current->end_data;
    tmp = page + 4096;
    while (i-- > 0) {
        tmp--;
        *(char *)tmp = 0;
    }
    if (put_page(page, address))
        return;
    free_page(page);
    oom();
}

void mem_init(long start_mem, long end_mem)
{
    int i;

    HIGH_MEMORY = end_mem;
    for (i = 0; i < PAGING_PAGES; i++)
        mem_map[i] = USED;
    i = MAP_NR(start_mem);
    end_mem -= start_mem;
    end_mem >>= 12;             // 可分配内存的总页面数
    while (end_mem-- >0)
        mem_map[i++]=0;
}
